//自己
class Solution {
public:
    //后序
    void MergerSort(vector<int>& nums, int left, int right, int* arr)
    {
        //1.限制条件
        if (left == right)//只有一个元素, 直接有序
            return;

        int mid = left+(right-left)/2;
        MergerSort(nums, left, mid, arr);
        MergerSort(nums, mid+1, right, arr);
        
        //处理
        //2.取小归并
        int i=left, j=mid+1, temp = left;
        //int arr[right-left+1];//c99后,允许定义可变数组, 但不能初始化; 临时数组, 防止全在原数组操作造成数据覆盖
        while (i <= mid && j<=right)
        {
            //cout << nums[i] << " " << nums[j] << endl;
            if (nums[i] < nums[j])
                arr[temp++] = nums[i++];//arr与nums位置一一对应
            else
                arr[temp++] = nums[j++];
        }

        //3.哪个区间剩, 就把哪个区间剩余有序元素放进arr
        while (i <= mid)
            arr[temp++] = nums[i++];
        while (j <= right)
            arr[temp++] = nums[j++];

        //4.把arr元素, 放回nums
        for (int i=left; i<=right; i++)
            nums[i] = arr[i];
    }

    vector<int> sortArray(vector<int>& nums) {
        //merger排序
        int n = nums.size();
        int* arr = new int[n];
        MergerSort(nums, 0, n-1, arr);
        delete[] arr;
        return nums;
    }
};
//时间: O(N*logN)
//空间: O(N+logN)

//答案
class Solution {
    vector<int> v1;
public:
    void MergerSort(vector<int>& nums, int left, int right)
    {
        //1.限制条件
        if (left == right)//只有一个元素, 直接有序
            return;

        int mid = left+(right-left) / 2;
        MergerSort(nums, left, mid);
        MergerSort(nums, mid+1, right);
        
        //2.取小归并
        int cur1=left, cur2=mid+1, i = 0;
        while (cur1 <= mid && cur2<=right)
            v1[i++] = nums[cur1]<=nums[cur2] ? nums[cur1++] : nums[cur2++];

        //3.哪个区间剩, 就把哪个区间剩余有序元素放进arr
        while (cur1 <= mid)
            v1[i++] = nums[cur1++];
        while (cur2 <= right)
            v1[i++] = nums[cur2++];

        //4.把v1元素, 放回nums
        for (int i=left; i<=right; i++)
            nums[i] = v1[i-left];//把v1中元素放入nums
    }

    vector<int> sortArray(vector<int>& nums) {
        //merger排序
        int n = nums.size();
        v1.resize(n);//扩容
        MergerSort(nums, 0, n-1);
        return nums;
    }
};
//时间: O(N*logN)
//空间: O(N+logN)